package priv.conceit.study.leetcode.medium;

import java.util.Objects;
/**
 * 编号98
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树
 * <p>
 * <a href="https://leetcode-cn.com/problems/validate-binary-search-tree/"/>
 * 假设一个二叉搜索树具有如下特征
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 既左结点都比当前节点小，右节点都比当前节点大
 * 示例2这种
 * 4得左结点3，小于5，所以此树不成立
 *
 * <p>
 * 示例 1:
 *   2
 *  / \
 * 1   3
 * 输出: true
 * <p>
 * 示例 2:
 *    5
 *   /  \
 *  1    4
 *      /  \
 *     3    6
 * <p>
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 * 根节点的值为 5 ，但是其右子节点值为 4 。
 * <p>
 * <p>
 * 1-深度优先 dfs
 * <p>
 * 2-递归
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/22
 */
public class ValidateBinarySearchTree {

	public static void main(String[] args) {

	}

	public boolean isValidBST(TreeNode root) {
		if(Objects.isNull(root)){
			return Boolean.TRUE;
		}


		return dfs(root);
	}


	/**
	 * 深度优先
	 * 使用 栈 数据结构来完成
	 *
	 * 右节点优先进栈
	 * 左结点出栈优先处理
	 *
	 *
	 *
	 * @param root
	 * @return
	 */
	public boolean dfs(TreeNode root) {
		// TODO: 2019/8/2
		if(Objects.isNull(root)){
			return Boolean.TRUE;
		}





		return Boolean.TRUE;
	}



	public boolean recursion(TreeNode root) {
		return Boolean.TRUE;
	}



	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) {
			val = x;
		}
	}

}
